1. Field of the Invention
The present invention relates to image analysis. More particularly, the present invention relates to a method and apparatus for detecting changes in an image and performing image compression using a statistical wavelet approach.
2. Background Information
Wavelet analysis of signals and images allows analysis of signals according to scale. Data associated with a signal or image can be divided into different frequency components and analyzed according to an appropriate scale for each respective component. Wavelet functions can be used to represent or approximate signal behavior at various points while satisfying certain mathematical constraints. Wavelet analysis is advantageous in analyzing signals or images having discontinuities or sharp spikes or edges. See, for example, “An Introduction To Wavelets”, Gaps, Amara, 1995, Institute of Electrical and Electronic Engineers, the subject matter of which is incorporated herein by reference.
The use of analytic functions to allow for the approximation and, thus characterization of signal behavior is not new. Fourier analysis which can be used to approximate signal behavior using the superposition of known continuous, non-local functions was developed by Joseph Fourier in the early 1800s and is concerned primarily with frequency analysis. Wavelet analysis in contrast is focused on continuous refinements in scale of the approximating functions and allows for the analysis of the instantaneous behavior of a signal rather than its continuous behavior across the time domain. Wavelets allow for the approximation of finite signals having very sharp signal characteristics.
Wavelet analysis involves adopting a wavelet prototype function called an analyzing wavelet or mother wavelet. Frequency and time analysis can be performed with high and low frequency versions of the prototype wavelet. A wavelet expansion can then be used to represent the signal. Coefficients can be derived for the linear combination of wavelet functions which approximate the signal and can be used for data operations. Moreover, certain coefficients, for example, those below a selected threshold, can be truncated without significant effect, allowing a sparse representation of the signal, and giving rise to advantages in the area of, for example, data compression.
An objective of many data compression schemes is to produce the most efficient representation of a block of information with minimal cost in terms of overhead and processing. Conservative data compression schemes avoid changing input data. Other approaches reduce data to essential features or information content and store only those features or content. For compression approaches which reduce data to be successful, the correct reduction or filter step should be used to preserve essential data features.
While wavelet and Fourier transforms are both useful analytical tools and share similarities, they are different in that wavelet transforms, unlike Fourier transforms, are localized in space. Spatial localization and frequency localization properties associated with wavelets allow functions to be transformed sparsely into the wavelet domain. Moreover, since wavelet transforms are not constrained by a single set of basis functions as in Fourier transforms which use sine and cosine functions, information which might be obscured using Fourier analysis is made available using wavelet transforms. In fact, different families of wavelet basis functions can be selected based on tradeoffs involving desired spatial localization versus, for example, smoothness.
An analyzing wavelet or mother wavelet Φ(x) can be applied to approximate a signal by shifting and scaling, resulting in a family of wavelet functions which comprise the basis:Φ(s,l)(x)=2−s/2Φ(2−sx−l)  (1)where s and l are integers that scale and shift the mother function Φ to generate the wavelet family such as the Daubechies family (there are several well known so-called wavelet “families” named after their discoverers). The variable s determines the width of the wavelet and the location index l determines the position of the particular wavelet. The mother function Φ can be re-scaled by powers of 2 and shifted by integers giving rise to an interesting property of self-similarity. By understanding the properties of mother function Φ, the properties of the wavelet basis, as shown in equation (1) are automatically known.
To apply equation (1) to a set of data, a scaling equation can be used:
                              W          ⁡                      (            x            )                          =                              ∑                          k              =                              -                1                                                    N              -              2                                ⁢                                                    (                                  -                  1                                )                            k                        ⁢                          c                              k                +                1                                      ⁢                          Φ              ⁡                              (                                                      2                    ⁢                    x                                    +                  k                                )                                                                        (        2        )            where W(x) is the scaling function for the mother function Φ, and ck are the wavelet coefficients. The wavelet coefficients should satisfy the linear and quadratic constraints of the form:
                                                                                                              ∑                                          k                      =                      0                                                              N                      -                      1                                                        ⁢                                      c                    k                                                  =                2                            ,                                                                                                                                                      ∑                                      k                    =                    0                                                        N                    -                    1                                                  ⁢                                                      c                    k                                    ⁢                                      c                    l                                                              =                              2                ⁢                                                                  ⁢                                  δ                                      l                    ,                    0                                                                                                          (        3        )            where δ is the delta function and l is the location index. Coefficients {c0, . . . , cn} can be thought of as filter coefficients, with values being placed, for example, in a transformation matrix, which can then be applied to a data vector. Coefficients applied in this manner can operate, for example, as a smoothing filter, low pass filter, and/or as a high pass filter (which tends to accentuate detail contained within the data).
Another area of interest in signal and image processing and analysis is associated with change detection. Change detection deals with changes in signals which, in some cases, can be discontinuous in nature. Change detection can be used for signal or system modeling, and can play a role in, for example, pattern recognition, video monitoring, and other analysis associated with dynamic systems. Accordingly, methods have be developed in both on-line detection and off-line detection to serve different purposes.
One system developed for indicating changes between images is described in U.S. Pat. No. 5,500,904 to Markandey et al (hereinafter “Markandey”). Therein, a sequence of images is sensed and processed images are generated using previous images. An optical flow field can be generated indicating changes between images. The subject matter of the Markandey patent is hereby incorporated within by reference.
Other systems, such as described, for example, in U.S. Pat. No. 5,563,960 to Shapiro, are directed to emphasis on a selected region of an image to be compressed. Shapiro describes a scanning order for wavelet coefficients to provide a more efficient compression scheme. The subject matter of the Shapiro patent is hereby incorporated within by reference.
Another method for handling compression is disclosed in U.S. Pat. No. 5,539,841 (“Huttenlocher”), the subject matter of which is incorporated herein by reference. Huttonlocher describes a method for comparing image sections, referred to as tokens.